Search for: All records

In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks. 

Abstract The Generalized Hamming weights and their relative version, which generalize the minimum distance of a linear code, are relevant to numerous applications, including coding on the wire-tap channel of type II,t-resilient functions, bounding the cardinality of the output in list decoding algorithms, ramp secret sharing schemes, and quantum error correction. The generalized Hamming weights have been determined for some families of codes, including Cartesian codes and Hermitian one-point codes. In this paper, we determine the generalized Hamming weights of decreasing norm-trace codes, which are linear codes defined by evaluating sets of monomials that are closed under divisibility on the rational points of the extended norm-trace curve given by$$x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y$$ $x^u=y^{q^{s-1}}+y^{q^{s-2}}+\cdots +y$over the finite field of cardinality$$q^s$$ $q^s$, whereuis a positive divisor of$$\frac{q^s - 1}{q - 1}$$ $\frac{q^s-1}{q-1}$. As a particular case, we obtain the weight hierarchy of one-point norm-trace codes and recover the result of Barbero and Munuera (2001) giving the weight hierarchy of one-point Hermitian codes. We also study the relative generalized Hamming weights for these codes and use them to construct impure quantum codes with excellent parameters. 

The ability of a linear error-correcting code to recover erasures is connected to influences of particular monotone Boolean functions. These functions provide insight into the role that particular coordinates play in a code’s erasure repair capability. We consider directly the influences of coordinates of a code. We describe a family of codes, called codes with minimum disjoint support, for which all influences may be determined. As a consequence, we find influences of repetition codes and certain distinct weight codes. Computing influences is typically circumvented by appealing to the transitivity of the automorphism group of the code. Some of the codes considered here fail to meet the transitivity conditions required for these standard approaches, yet we can compute them directly.